/**
 * https://leetcode.cn/problems/find-if-path-exists-in-graph/submissions/572737112/
 * 1971. 寻找图中是否存在路径
 * easy,陈贝纯 2024.10.14
 * 并查集
 */

class Solution {
public:
    bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {
        vector<vector<int>> adj(n);
        for(int i=0;i<edges.size();++i){
            adj[edges[i][0]].push_back(edges[i][1]);
            adj[edges[i][1]].push_back(edges[i][0]);
        }
        vector<bool> visit(n);
        queue<int> q;
        q.emplace(source);
        visit[source]=true;
        while(!q.empty()){
            int t=q.front();
            q.pop();
            if(visit[destination])
            return true;
            for(int next:adj[t]){
                if(!visit[next]){
                    q.emplace(next);
                    visit[next]=true;
                }
            }
        }
        return false;
    }
};